package com.wdc.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

@SuppressWarnings("aLL")
public class E01Leetcode77 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public  List<List<Integer>> combine(int n, int k) {
        backtracking(1,n,k);
        return result;
    }

    void backtracking(int stratIdex ,int n , int k){
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        //选择本层集合中元素
        for (int i = stratIdex; i <= n; i++) {
            //处理节点
            path.add(i);
            backtracking(i + 1,n,k );
            path.removeLast();

        }
    }


    //优化版本
//    void backtracking2(int stratIdex ,int n , int k){
//        //终止条件
//        if (path.size() == k){
//            result.add(new ArrayList<>(path));
//            return;
//        }
//
//        //选择本层集合中元素
//        for (int i = stratIdex; i <= n - (k - path.size()) + 1; i++) {
//            //处理节点
//            path.add(i);
//            backtracking(i + 1,n,k );
//            path.removeLast();
//
//        }
//    }

    void backtracking2(int n,int k,int startIndex){
        //结束条件
        if (path.size() == k){
            //加入集合
            result.add(new ArrayList<>(path));
            return;
        }

        //n - (k - path.size()) + 1;
        for (int i = startIndex; i <= n - (k - path.size()) + 1 ; i++) {
            //处理节点,加入路径中
            path.add(i);
            //递归调用
            backtracking(n,k,i + 1);
            //回溯
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        E01Leetcode77 e01Leetcode77 = new E01Leetcode77();
        System.out.println(e01Leetcode77.combine(4, 2));

    }




}
